<html>
<head><meta charset="utf-8"><title>default to unstable sort when sorting primitive type slices · t-libs · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/index.html">t-libs</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html">default to unstable sort when sorting primitive type slices</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="209610962"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209610962" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matthiaskrgr <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209610962">(Sep 10 2020 at 08:52)</a>:</h4>
<p>leonardo-m had the idea here: <a href="https://github.com/rust-lang/rust/pull/76541#issuecomment-689852777">https://github.com/rust-lang/rust/pull/76541#issuecomment-689852777</a></p>
<p>Could we add a custom  slice sort impl for slices of primitive types which uses <code>sort::quicksort</code> (what <code>.unstable_sort()</code> uses) instead of <code>merge_sort</code> (what stable <code>.sort()</code> uses)?</p>
<p>Using unstable sort should have more performance and if we have slices of primitives like <code>u8</code>, it does not matter which 1 comes first in <code>[1, 1, 2, 3]</code> (we don't need to retain original order since there is no extra data but that primitive value).</p>



<a name="209672310"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209672310" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pickfire <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209672310">(Sep 10 2020 at 16:26)</a>:</h4>
<p>As we already have <code>unstable_sort</code>, defaulting it to <code>sort</code> may be surprising. If people already specified <code>unstable_sort</code> but they get <code>sort</code>, usually one would feel surprised. I don't know if this is a good idea unless it's always faster and better.</p>



<a name="209672488"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209672488" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pickfire <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209672488">(Sep 10 2020 at 16:27)</a>:</h4>
<p>But say if we only have <code>sort</code> but no <code>unstable_sort</code> then this would be a good idea since we can just do the optimization on the underlying layer probably without any breaking changes or impact on users.</p>



<a name="209672510"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209672510" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209672510">(Sep 10 2020 at 16:27)</a>:</h4>
<p><span class="user-mention" data-user-id="225422">@pickfire</span> Maybe I'm misreading what you said, but this is about switching sort() to unstable_sort() not the other way around.</p>



<a name="209672582"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209672582" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209672582">(Sep 10 2020 at 16:28)</a>:</h4>
<p>It would ~never make sense to pay the price of sort() for unstable_sort(), I expect.</p>



<a name="209672807"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209672807" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pickfire <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209672807">(Sep 10 2020 at 16:29)</a>:</h4>
<p><span class="user-mention" data-user-id="116122">@simulacrum</span> So you mean when users do <code>sort</code> on primitive slices, they get <code>unstable_sort</code> instead?</p>



<a name="209672815"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209672815" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209672815">(Sep 10 2020 at 16:29)</a>:</h4>
<p>Yes.</p>



<a name="209672857"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209672857" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pickfire <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209672857">(Sep 10 2020 at 16:30)</a>:</h4>
<p>But wouldn't <code>unstable_sort</code> still be available?</p>



<a name="209672961"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209672961" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209672961">(Sep 10 2020 at 16:30)</a>:</h4>
<p>unstable_sort is available, but you may not know if you can use it in a generic context, for one thing. This is just an optimization, could really be done for any type with structural equality probably?</p>



<a name="209673018"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209673018" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pickfire <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209673018">(Sep 10 2020 at 16:31)</a>:</h4>
<p>But what if users really want <code>sort</code> but not <code>unstable_sort</code>?</p>



<a name="209673379"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209673379" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209673379">(Sep 10 2020 at 16:33)</a>:</h4>
<p>...why would they? And how can they tell the difference?</p>



<a name="209673383"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209673383" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pickfire <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209673383">(Sep 10 2020 at 16:33)</a>:</h4>
<p>Ah, if I am not mistaken so <code>sort</code> is the exact equivalent as <code>sort_unstable</code> for primitives types (likely those that implements <code>Copy</code>) except being slower? Am I correct?</p>



<a name="209673565"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209673565" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209673565">(Sep 10 2020 at 16:34)</a>:</h4>
<p>For all types with structural equality and comparison operations</p>



<a name="209676317"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209676317" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Steven Fackler <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209676317">(Sep 10 2020 at 16:54)</a>:</h4>
<p>I don't know what the status of the specialization moratorium is, but it seems plausible to do this if unstable sort is in fact faster in these cases</p>



<a name="209678329"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209678329" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209678329">(Sep 10 2020 at 17:07)</a>:</h4>
<p>The docs claim so:</p>
<blockquote>
<p>When applicable, unstable sorting is preferred because it is generally faster than stable sorting and it doesn't allocate auxiliary memory.</p>
</blockquote>



<a name="209678497"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209678497" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209678497">(Sep 10 2020 at 17:08)</a>:</h4>
<p>on <code>unstable_sort</code>:</p>
<blockquote>
<p>It is typically faster than stable sorting, except in a few special cases, e.g., when the slice consists of several concatenated sorted sequences.</p>
</blockquote>



<a name="209684760"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209684760" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209684760">(Sep 10 2020 at 17:58)</a>:</h4>
<p>I did actually run into someone on Discord (I think it was) the other day who was asking how to merge several sorted sequences, and I suggested <code>sort</code> for exactly that reason.  (Obligatory <a href="https://xkcd.com/1172/">https://xkcd.com/1172/</a>)</p>



<a name="209686307"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209686307" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209686307">(Sep 10 2020 at 18:09)</a>:</h4>
<p>Pondering: this would have to be for <code>.sort()</code> only, right?  <code>.sort_by_key(|x| x.some_u32)</code> needs to still be stable...</p>



<a name="209686820"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209686820" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209686820">(Sep 10 2020 at 18:12)</a>:</h4>
<p>Hm, I think so, yes. We don't know what the closures does so cannot assume it is an identity function</p>



<a name="209703527"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209703527" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209703527">(Sep 10 2020 at 20:17)</a>:</h4>
<p>In theory, you could assume based on specialization that if the element type and the key type are both simple indistinguishable-if-equal types that <code>sort_unstable</code> is fine, but it's not clear that it's worth doing.</p>



<a name="209703636"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209703636" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209703636">(Sep 10 2020 at 20:18)</a>:</h4>
<p><code>sort_by_key</code> doesn't provide the index, just the element by value, so if the element is a <code>u64</code> and the returned key is a <code>u32</code> (for instance) then you could use <code>sort_unstable</code>.</p>



<a name="209704915"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209704915" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209704915">(Sep 10 2020 at 20:29)</a>:</h4>
<p>Hm, not necessarily, because the u64 could be an index into, say, a HashMap&lt;u64, SomeComplexType&gt;</p>



<a name="209704974"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209704974" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209704974">(Sep 10 2020 at 20:30)</a>:</h4>
<p>oh, though I guess you still can't derive whether we swapped two u64s or not</p>



<a name="209704981"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209704981" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209704981">(Sep 10 2020 at 20:30)</a>:</h4>
<p>yeah that seems right then</p>



<a name="209707799"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209707799" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209707799">(Sep 10 2020 at 20:55)</a>:</h4>
<p>If that's straightforward to do with <code>min_specialization</code> then by all means, but if it isn't then that seems fine too.</p>



<a name="209717110"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209717110" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209717110">(Sep 10 2020 at 22:22)</a>:</h4>
<p><span class="user-mention" data-user-id="239881">@Josh Triplett</span> the element and key types both being indistinguishable-if-equal is unsufficient.  Demo with them both being i32: <a href="https://play.rust-lang.org/?version=stable&amp;mode=debug&amp;edition=2018&amp;gist=4c66ebd6b1344872e87eeb20f6c114bc">https://play.rust-lang.org/?version=stable&amp;mode=debug&amp;edition=2018&amp;gist=4c66ebd6b1344872e87eeb20f6c114bc</a></p>
<p>(I think it also requires that the key function is injective.)</p>



<a name="209717176"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209717176" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209717176">(Sep 10 2020 at 22:23)</a>:</h4>
<p><span class="user-mention" data-user-id="125270">@scottmcm</span> You're right, strictly speaking that's valid according to the contract of the function. Cute!</p>



<a name="209717276"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209717276" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209717276">(Sep 10 2020 at 22:24)</a>:</h4>
<p>So you can partition elements into arbitrary order-preserved partitions that way.</p>



<a name="209717352"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209717352" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209717352">(Sep 10 2020 at 22:25)</a>:</h4>
<p>Yup.  We don't have a dedicated equivalent of C++'s <code>stable_partition</code>, so <code>.sort_by_key(predicate)</code> is the simplest way I know to do that right now.</p>



<a name="209717489"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209717489" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209717489">(Sep 10 2020 at 22:27)</a>:</h4>
<p>We could, and possibly should, provide a <code>partition_by_key</code> function.</p>



<a name="209717680"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209717680" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209717680">(Sep 10 2020 at 22:30)</a>:</h4>
<p>Well we have <a href="https://doc.rust-lang.org/nightly/core/iter/trait.Iterator.html#method.partition_in_place">https://doc.rust-lang.org/nightly/core/iter/trait.Iterator.html#method.partition_in_place</a>, but it's unstable -- in both senses of the word.  I don't remember whether a stable partition is doable in O(1) extra space.  I figure probably not, or quicksort would be stable more often.</p>



<a name="209717770"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209717770" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209717770">(Sep 10 2020 at 22:30)</a>:</h4>
<p>In O(1) extra space and no worse than n log n time?</p>



<a name="209717846"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209717846" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209717846">(Sep 10 2020 at 22:31)</a>:</h4>
<p>If you have a boolean predicate, it absolutely is.</p>



<a name="209717894"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209717894" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209717894">(Sep 10 2020 at 22:32)</a>:</h4>
<p>If you have arbitrary keys, I don't know if there's an algorithm that would allow that.</p>



<a name="209717981"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209717981" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209717981">(Sep 10 2020 at 22:33)</a>:</h4>
<p>But with a boolean predicate, it's trivial: track the next insertion indexes for false/true, walk the list forward, apply the predicate, put the element at the index and increment/decrement the index, then reverse the second set of elements.</p>



<a name="209718008"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209718008" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209718008">(Sep 10 2020 at 22:33)</a>:</h4>
<p>The <a href="https://en.cppreference.com/w/cpp/algorithm/stable_partition">C++ requirements</a> suggest there's just the simple ones -- O(n) time &amp; space, or O(n lg n) time without extra space.</p>



<a name="209718066"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209718066" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209718066">(Sep 10 2020 at 22:34)</a>:</h4>
<p>Ah, sorry, I just realized that by O(1) extra space you mean "in place".</p>



<a name="209718075"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209718075" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209718075">(Sep 10 2020 at 22:34)</a>:</h4>
<p>(as opposed to "without any auxiliary space".)</p>



<a name="209718117"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209718117" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209718117">(Sep 10 2020 at 22:35)</a>:</h4>
<p>Ah, right -- sorry for confusion.  (We do have <code>Iterator::partition</code> if allocating O(n) space is ok.)</p>



<a name="209718141"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209718141" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209718141">(Sep 10 2020 at 22:35)</a>:</h4>
<p>I think if you want to guarantee that you call the predicate only once per element then the C++ requirements are the best you can do.</p>



<a name="209718228"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209718228" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209718228">(Sep 10 2020 at 22:36)</a>:</h4>
<p>I think it <em>might</em> be possible to do better if you don't mind doing two passes and two sets of calls to the predicate, but that's probably not ideal.</p>



<a name="209718253"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/default%20to%20unstable%20sort%20when%20sorting%20primitive%20type%20slices/near/209718253" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/default.20to.20unstable.20sort.20when.20sorting.20primitive.20type.20slices.html#209718253">(Sep 10 2020 at 22:37)</a>:</h4>
<p>And conveniently we have <code>.sort_by_cached_key</code> for only calling the predicate once per item then doing an unstable sort by the composite key ;)</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>